import java.util.Iterator;

/**
 * Find the Augment path in the given graph
 * @author 捣蛋鬼x
 *
 */
public class FindPath {
	static int maxFlow; 
	static boolean path = false;
	/**
	 * 
	 */
	public FindPath() {
		super();
	}
/**
 * Find the augment path from s to t using depth first serch
 * @param G SimpleGraph Input
 * @param s start point
 * @param t end point
 * @param p empty SimpleGraph to store path
 * @param d scaling parameter used in ScalingFF
 * @return
 */
	public static SimpleGraph DFS (SimpleGraph G, Vertex s, Vertex t, SimpleGraph p, int d) {
		Vertex v;
		Edge e;
		VertexData vData;
		Iterator i;
		SimpleGraph newPath;
		path = false;

//Set s to be visited 
		VertexData data = new VertexData(true);
		s.setData(data);
//Add s into p		
		p.vertexList.add(s);
//Find all edage linked to s
		for (i= G.incidentEdges(s); i.hasNext(); ) {
			e = (Edge) i.next();
			v = G.opposite(s, e);
//Check residual flow
			if (!( (VertexData) v.getData()).isVisited() &&
					(v == e.getSecondEndpoint() && ((EdgeData) e.getData()).getAvailable() > d ||
					v == e.getFirstEndpoint() && ((EdgeData) e.getData()).getFlow() > d)) {

				if (v == t){
					p.edgeList.add(e);
					p.vertexList.add(v);
					return p;
				}
         
				p.edgeList.add(e);
				newPath = DFS(G, v, t, p, d);
				if (newPath.vertexList.getLast() == t) {
					maxFlow((EdgeData) ((Edge) newPath.edgeList.getFirst()).getData());
					isPath();
					return newPath;
				}
				p.edgeList.removeLast();
			}
			( (VertexData) s.getData()).setVisited(true);
		}

		p.vertexList.removeLast();
		return p;
	}

	private static Boolean isPath() {
		return path = true;

	}

	private static int maxFlow(EdgeData data) {
		maxFlow += data.getFlow();
		return maxFlow;

	}

	public static void main(String[] args) throws Exception {
		SimpleGraph G = new SimpleGraph();
		Vertex s = null,t=null, v;
		Edge e;
		SimpleGraph path;
		Iterator i;
		EdgeData edata;
		VertexData vdata;
//Test code
		GraphInput.LoadSimpleGraph(G, "/Users/stflaptop/Documents/workspace/FlowNetwork/random.txt");
		for (i= G.vertices(); i.hasNext(); ) {
            Vertex v1 = (Vertex) i.next();
            if (v1.getName().equals("s")) s=v1;
            else if (v1.getName().equals("t")) t=v1;
            }
		System.out.println("Graph edges");
		for (i = G.edges(); i.hasNext(); ){
			e = (Edge) i.next();
			try {
				 edata = new EdgeData(((Double)e.getData()).intValue(),0);
			} catch (Exception e2) {
				// TODO: handle exception
				System.out.println("stop");
				return;
			}
			//edata = (EdgeData) e.getData();
			System.out.println("Edge: " + e.getName() + " " 
					+ e.getFirstEndpoint().getName() + "-" 
					+ e.getSecondEndpoint().getName() + " "
					+ edata.getFlow() + "/" + edata.getCapacity());
		}
		System.out.println();

		path = DFS(G, s, t, new SimpleGraph(), 2);

		for (i = G.vertices(); i.hasNext(); ){
			v = (Vertex) i.next();
			vdata = (VertexData) v.getData();
			vdata.setVisited(false);			
		}

	}
}
